import sun.reflect.generics.tree.Tree;

import java.util.List;
import java.util.Stack;

class TreeNode{
    public int val;
    TreeNode left;
    TreeNode right;
    public TreeNode(int val){
        this.val = val;
    }
}
public class Test {
    //给定一个二叉树, 找到该树中两个指定节点的最近公共祖先:"最近公共祖先的定义为：
    // “对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，
    // 满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）"

    //方法1：递归
    public TreeNode lowestCommonAncestor1(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null){
            return null;
        }
        if (p == root || q == root){
            return root;
        }
        TreeNode left = lowestCommonAncestor1(root.left,p,q);
        TreeNode right = lowestCommonAncestor1(root.right,p,q);
        if (left != null && right != null){
            return root;
        }else if (left != null){
            return left;
        }else {
            return right;
        }
    }
    //方法2：使用栈
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q){
        Stack<TreeNode> s1 = new Stack<>();
        Stack<TreeNode> s2 = new Stack<>();
        boolean b1 = getPath(root, p, s1);
        boolean b2 = getPath(root, q, s2);
        int size1 = s1.size();
        int size2 = s2.size();
        if (size1 > size2){
            int size = size1 - size2;
            while(size != 0){
                s1.pop();
                size--;
            }
        }else {
            int size = size2 - size1;
            while(size != 0){
                s2.pop();
                size--;
            }
        }
        while (!s1.empty() && !s2.isEmpty()){
            TreeNode node1 = s1.pop();
            TreeNode node2 = s2.pop();
            if (node1 == node2){
                return node1;
            }
        }
        return null;
    }
    public boolean getPath(TreeNode root, TreeNode node, Stack<TreeNode> stack){
        if (root == null){
            return false;
        }
        stack.push(root);
        if (root == node){
            return true;
        }
        boolean left = getPath(root.left,node,stack);
        if (left == true){
            return true;
        }
        boolean right = getPath(root.right, node, stack);
        if (right == true){
            return true;
        }
        stack.pop();
        return false;
    }
    //二叉树前序非递归遍历实现
    public void preorderTraversal(TreeNode root){
        Stack<TreeNode> stack = new Stack<>();
        TreeNode cur = root;
        while (cur != null || !stack.isEmpty()){
            while (cur != null){
                stack.push(cur);
                cur = cur.left;
            }
            TreeNode node = stack.pop();
            System.out.print(node.val + " ");
            cur = node.right;
        }
    }
}
